//Det()=0x2b  2010-08-05 14:31:02
//
//比如在边线上DP...
//
//Det()=0x2b  2010-08-05 14:31:27
//
//因为边线子只会被同根边线的影响..
//
//Det()=0x2b  2010-08-05 14:31:49
//
//所以可以单独预处理..所有状态的最后可能性
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>

#define N 8
#define MAP_SIZE 324 //N * N * 4
#define P_MAP MAP[N+1][N+1]
#define INF (0x7fffffff - 1)

int numnode;
struct POS {
	int x,y;
	POS *next;
};

struct POS_D {
	int x,y;
	bool dir[8];
};

struct CAN {
	bool *dir;
	int col;
	int deb;
};

namespace MAP{

	//consts
	const int DET[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
	const int PATH[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
	//

	int map[N+1][N+1]; //0 NOT 2 Black 1 white
	CAN map_black_dir[N+1][N+1];
	CAN map_white_dir[N+1][N+1];

	//useful fuctions
	void Can_drop_black(int P_MAP,POS_D* PUT_POSS_BLACK,POS* BORDER,int &PUT_NUM_BLACK);//create a list
	void Can_drop_white(int P_MAP,POS_D* PUT_POSS_WHITE,POS* BORDER,int &PUT_NUM_WHITE);//create a list

	int Drop_black(int x,int y,int P_MAP,bool dir[6],int Rec[63][2]);
	int Drop_white(int x,int y,int P_MAP,bool dir[6],int Rec[63][2]);
	void Remove_black(int x,int y,int P_MAP,int Rec[63][2]);
	void Remove_white(int x,int y,int P_MAP,int Rec[63][2]);

	void Start(int P_MAP,POS* BORDER,int &PUT_NUM_BLACK,int &PUT_NUM_WHITE);
	void Draw(int P_MAP,int x,int y);
	//

	//about the list
	POS* Find(int x,int y,POS* BORDER);
	void Del(int x,int y,POS* BORDER);
	void Expand(int x,int y,POS* BORDER,int P_MAP);
	void Expand(int x,int y,POS* BORDER,int P_MAP,bool *dir);//AI needs it
	void Resume(int x,int y,POS* BORDER);
	void view(POS*);
	//
}

namespace AI {
	const int K_NUM=2,K_TABL=9,K_REV=0;
	const int IMP_STEP = 11;
	const int V[N+1][N+1]={

		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0,9999999, -999,9995,9955,9955,9995, -999,9999999},
		{0,  -999, -999,  -9,  -9,  -9,  -9, -999,	-999},
		{0,  9995,   -9,  33,  33,  33,  33,   -9,  9995},
		{0,  9955,   -9,  33,   0,   0,  33,   -9,  9955},
		{0,  9955,   -9,  33,   0,   0,  33,   -9,  9955},
		{0,  9995,   -9,  33,  33,  33,  33,   -9,  9995},
		{0,  -999, -999,  -9,  -9,  -9,  -9, -999,  -999},
		{0,9999999, -999,9995,9955,9955,9995, -999,9999999}
		/*	
			{0,0,0,0,0},
			{0,9999,-999,-999,9999},
			{0, -99,   0,   0, -99},
			{0, -99,   0   ,0, -99},
			{0,9999,-999,-999,9999}*/
	};

	int Get_value(int P_MAP,int B_NUM,int W_NUM,int dep);
	void AI_next(int P_MAP,POS *BD,int NOW_BNUM,int NOW_WNUM,int &Fx,int &Fy);

	int Black_search(int P_MAP,int,int,int,int,int,bool);
	int White_search(int P_MAP,int,int,int,int,int,bool);
	//P_MAP mem used is only about the deepth!
	POS* NOW_BORDER;
	int MAX_DEP=8;
	int Next_x,Next_y;
};


using namespace MAP;

int main() {

	POS* border=new POS;
	POS_D put_POSS_BLACK[257]; int put_NUM_BLACK;
	POS_D put_POSS_WHITE[257]; int put_NUM_WHITE;
	int NOW_BNUM = 2,NOW_WNUM = 2;
	int dir[6],tc,x = 0,y = 0,cnt = 0;
	int Rec[63][2];
	bool flag;

	FILE *output = fopen("yourstep.out","w");
	fclose(output);
	srand(time(0));
	memset(dir,0,sizeof(dir));

	printf("Lady first? 1 Yes/0 No\n");
	scanf("%d",&tc);

	Start(map,border,put_NUM_BLACK,put_NUM_WHITE);
	while (1)
	{
		Can_drop_black(map,put_POSS_BLACK,border,put_NUM_BLACK);
		Can_drop_white(map,put_POSS_WHITE,border,put_NUM_WHITE);
		numnode=0;

		memset(map_black_dir,0,sizeof(map_black_dir));
		memset(map_white_dir,0,sizeof(map_white_dir));

		for (int i=1; i<=put_NUM_BLACK; i++)
		{
			map_black_dir[put_POSS_BLACK[i].x][put_POSS_BLACK[i].y].dir=put_POSS_BLACK[i].dir;
			map_black_dir[put_POSS_BLACK[i].x][put_POSS_BLACK[i].y].col=2;
		}
		for (int i=1; i<=put_NUM_WHITE; i++)
		{
			map_white_dir[put_POSS_WHITE[i].x][put_POSS_WHITE[i].y].dir=put_POSS_WHITE[i].dir;
			map_white_dir[put_POSS_WHITE[i].x][put_POSS_WHITE[i].y].col=1;
		}
		Draw(map,x,y);
		if (!put_NUM_BLACK && !put_NUM_WHITE) break;//termin

		if (!tc)
		{
			if (!put_NUM_BLACK) {tc=1;continue;} //PASS
			AI::AI_next(map,border,NOW_BNUM,NOW_WNUM,x,y);//thinking...
			std::cout<<x<<' '<<y<<std::endl;
			int tmp = Drop_black(x,y,map,map_black_dir[x][y].dir,Rec);
			NOW_WNUM -= tmp;
			NOW_BNUM += tmp + 1;
			Expand(x,y,border,map);
			Del(x,y,border);
			printf("[%d] Turn %d: \"Stupid\" dropped at (%d,%d)\no:%.2d x:%.2d\n",numnode,++cnt,x,y,NOW_WNUM,NOW_BNUM);
		}
		else
		{
			if (!put_NUM_WHITE) {tc=0; continue;}
			flag=1;
			while (flag)
			{
				scanf("%d %d",&x,&y);
				output = fopen("yourstep.out","a");
				fprintf(output,"%d %d\n",x,y);
				fclose(output);
				if (map_white_dir[x][y].col==1)
				{
					int tmp = Drop_white(x,y,map,map_white_dir[x][y].dir,Rec);
					NOW_BNUM -= tmp;
					NOW_WNUM += tmp + 1;
					Expand(x,y,border,map);
					Del(x,y,border);
					flag=0;
				}
				else printf("CANNOT PUT HERE!\n");
			}
		}
		tc ^= 1;
	}

	if (NOW_BNUM > NOW_WNUM) printf("AI WIN!\n");
	else if (NOW_BNUM < NOW_WNUM) printf("YOU are the WINNER!\n");
	else printf("Tie! - - \n");
	printf("Score: %d\n",NOW_BNUM - NOW_WNUM);
	return 0;
}
///////////////////    AI  Functions  ////////////////////

void AI::AI_next(int P_MAP,POS *BD,int NOW_BNUM,int NOW_WNUM,int &Fx,int &Fy) {

	NOW_BORDER=BD;
	int T_MAP[N + 1][N + 1];
	//	memmove(T_MAP,MAP,MAP_SIZE);
	if (N * N - NOW_BNUM - NOW_WNUM <= 18) MAX_DEP = IMP_STEP;
	int res = Black_search(MAP,NOW_BNUM,NOW_WNUM,1,-INF - 1,INF + 1,0);
	if (res == -INF) 
	{
		int PUT_NUM,rp;
		POS_D PUTPOSS[257];
		Can_drop_black(MAP,PUTPOSS,NOW_BORDER,PUT_NUM);
		rp = rand() % PUT_NUM + 1;
		Fx = PUTPOSS[rp].x;
		Fy = PUTPOSS[rp].y;
	}//I'll fail anyway..
	else
	{
		Fx = Next_x; 
		Fy = Next_y;
	}
}

int AI::Get_value(int P_MAP,int B_NUM,int W_NUM,int dep) {

	int res = 0;

	if (!B_NUM) return -INF;
	if (!W_NUM) return INF;
	if (B_NUM + W_NUM == N * N) return B_NUM > W_NUM ? INF : -INF;
	else if (dep == IMP_STEP) return B_NUM - W_NUM;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (MAP[i][j] == 2) res += V[i][j];
			else if (MAP[i][j] == 1) res -= V[i][j];
	//	res += (B_NUM * B_NUM - W_NUM * W_NUM) / 100;
	int c[4],d[4],st[4],ed[4];
	c[0] = c[1] = c[2] = c[3] = 0;
	d[0] = d[1] = d[2] = d[3] = 0;
	ed[0] = ed[1] = ed[2] = ed[3] = 0;
	for (int i = 1; i <= N; i++) 
	{
		if (MAP[i][1]) {c[0]++; d[0] += MAP[i][1]; st[0] = i;} else ed[0] = i;
		if (MAP[1][i]) {c[1]++; d[1] += MAP[1][i]; st[1] = i;} else ed[1] = i;
		if (MAP[i][N]) {c[2]++; d[2] += MAP[i][N]; st[2] = i;} else ed[2] = i;
		if (MAP[N][i]) {c[3]++; d[3] += MAP[N][i]; st[3] = i;} else ed[3] = i;
	}
	for (int i = 0; i < 4; i++)
	{
		int fac = 2;
		if (ed[i] < st[i]) fac = 10;
		else if (!ed[i]) fac = 100;
		else if (ed[i] - st[i] + 1 < c[i]) fac = 1;
		if (c[i] << 1 == d[i]) res += 999 * fac;
		else if (c[i] == d[i]) res -= 999 * fac;
	}
	return res;
}

int AI::Black_search(int P_MAP,int B_NUM,int W_NUM,int dep,int alpha,int beta,bool mark) { //machine drop black MAX


	POS_D PUTPOSS[257];
	int PUT_NUM,Rec[63][2];
	if (!W_NUM || dep==MAX_DEP) 
	{
		numnode++;
		return Get_value(MAP,B_NUM,W_NUM,dep);
	}

	Can_drop_black(MAP,PUTPOSS,NOW_BORDER,PUT_NUM);

	bool EXdir[8];
	int Dx,Dy,MAX=-INF;

	if (PUT_NUM)
	{
		for (int i=1; i<=PUT_NUM; i++)
		{
			memset(EXdir,0,sizeof(EXdir));
			Dx=PUTPOSS[i].x;
			Dy=PUTPOSS[i].y;

			Expand(Dx,Dy,NOW_BORDER,MAP,EXdir);
			Del(Dx,Dy,NOW_BORDER);
			int EAT_NUM=Drop_black(Dx,Dy,MAP,PUTPOSS[i].dir,Rec);//drop it!!!
			int S=White_search(MAP,B_NUM + EAT_NUM + 1,W_NUM - EAT_NUM,dep+1,alpha,beta,0); // calc
			Remove_black(Dx,Dy,MAP,Rec);
			for (int d=0; d<8; d++) if (EXdir[d]) Del(Dx+DET[d][0],Dy+DET[d][1],NOW_BORDER);
			Resume(Dx,Dy,NOW_BORDER);

			if (S>MAX) {MAX=S; if (dep == 1){Next_x = Dx; Next_y = Dy;}}
			if (MAX>=beta) return MAX;
			alpha=MAX;
		}
		return MAX;
	}
	else 
	{
		if (mark) return Get_value(MAP,B_NUM,W_NUM,dep);
		return White_search(MAP,B_NUM,W_NUM,dep,alpha,beta,1);
	}
}

int AI::White_search(int P_MAP,int B_NUM,int W_NUM,int dep,int alpha,int beta,bool mark) { //enemy drop white MIN


	POS_D PUTPOSS[257];
	int PUT_NUM,Rec[63][2];
	if (!B_NUM || dep==MAX_DEP) 
	{
		numnode++;
		return Get_value(MAP,B_NUM,W_NUM,dep);
	}

	Can_drop_white(MAP,PUTPOSS,NOW_BORDER,PUT_NUM);

	bool EXdir[8];
	int Dx,Dy,MIN=INF;

	if (PUT_NUM)
	{
		for (int i=1; i<=PUT_NUM; i++)
		{
			memset(EXdir,0,sizeof(EXdir));
			Dx=PUTPOSS[i].x;
			Dy=PUTPOSS[i].y;

			Expand(Dx,Dy,NOW_BORDER,MAP,EXdir);
			Del(Dx,Dy,NOW_BORDER);
			int EAT_NUM=Drop_white(Dx,Dy,MAP,PUTPOSS[i].dir,Rec);//drop it!!!
			int S=Black_search(MAP,B_NUM - EAT_NUM,W_NUM + EAT_NUM + 1,dep + 1,alpha,beta,0); // calc
			Remove_white(Dx,Dy,MAP,Rec);
			for (int d=0; d<8; d++) if (EXdir[d]) Del(Dx+DET[d][0],Dy+DET[d][1],NOW_BORDER);//
			Resume(Dx,Dy,NOW_BORDER);

			if (S<MIN) MIN=S;
			if (MIN<=alpha) return MIN;
			beta=MIN;
		}
		return MIN;
	}
	else
	{
		if (mark) Get_value(MAP,B_NUM,W_NUM,dep);
		return Black_search(MAP,B_NUM,W_NUM,dep,alpha,beta,1);
	}
}
///////////////////  MAP  Functions   /////////////////////

void MAP::Start(int P_MAP,POS* BORDER,int &PUT_NUM_BLACK,int &PUT_NUM_WHITE) {
	memset(MAP,0,sizeof(MAP));
	PUT_NUM_WHITE=0;
	PUT_NUM_BLACK=0;

	int mid=N>>1;

	MAP[mid][mid]=1; MAP[mid][mid+1]=2;
	MAP[mid+1][mid]=2; MAP[mid+1][mid+1]=1;

	Expand(mid,mid,BORDER,MAP); Expand(mid,mid+1,BORDER,MAP);
	Expand(mid+1,mid,BORDER,MAP); Expand(mid+1,mid+1,BORDER,MAP);
	//center position
}

void MAP::Draw(int P_MAP,int x,int y) {

	printf("  ");
	for (int i=1; i<=N; i++) printf("%2d",i);
	printf("\n");
	for (int i=1; i<=N; i++)
	{
		printf("%2d ",i);
		for (int j=1; j<=N; j++)
		{
			switch (MAP[i][j])
			{
				case 0:printf("."); break;
				case 1:printf("o"); break;
				case 2:printf("x"); break;
			}
			if (i == x && j == y) printf("]");
			else if (!(i == x && j + 1 == y)) printf(" "); 
			else printf("[");

		}
		printf("\n");
	}
	printf("\n");
}

int MAP::Drop_black(int x,int y,int P_MAP,bool dir[6],int Rec[63][2]) {

	int c=0;

	MAP[x][y]=2; //drop it
	Rec[0][0] = 0;
	for (int d=0; d<8; d++)
		if (dir[d])
			for (int nx=x+PATH[d][0],ny=y+PATH[d][1]; MAP[nx][ny]==1 && 1<=nx && nx<=N && 1<=ny && ny<=N; nx+=PATH[d][0],ny+=PATH[d][1],c++)
			{
				MAP[nx][ny]=2; //reverse
				Rec[++Rec[0][0]][0] = nx;
				Rec[Rec[0][0]][1] = ny;
			}
	return c;
}

int MAP::Drop_white(int x,int y,int P_MAP,bool dir[6],int Rec[63][2]) {

	int c=0;

	MAP[x][y]=1; //drop it
	Rec[0][0] = 0;
	for (int d=0; d<8; d++)
		if (dir[d])
			for (int nx=x+PATH[d][0],ny=y+PATH[d][1]; MAP[nx][ny]==2 && 1<=nx && nx<=N && 1<=ny && ny<=N; nx+=PATH[d][0],ny+=PATH[d][1],c++)
			{
				MAP[nx][ny]=1; //reverse
				Rec[++Rec[0][0]][0] = nx;
				Rec[Rec[0][0]][1] = ny;
			}
	return c;
}

void MAP::Remove_black(int x,int y,int P_MAP,int Rec[63][2]) {

	MAP[x][y]=0; //remove it
	for (int i = 1; i <= Rec[0][0]; i++)
		MAP[Rec[i][0]][Rec[i][1]] = 1;
}

void MAP::Remove_white(int x,int y,int P_MAP,int Rec[63][2]) {

	MAP[x][y]=0; //remove it
	for (int i = 1; i <= Rec[0][0]; i++)
		MAP[Rec[i][0]][Rec[i][1]] = 2;
}

void MAP::Can_drop_black(int P_MAP,POS_D* PUT_POSS_BLACK,POS* BORDER,int &PUT_NUM_BLACK) {

	PUT_NUM_BLACK=0;
	memset(PUT_POSS_BLACK,0,sizeof(POS_D)*257);

	for (POS* now=BORDER->next; now!=NULL; now=now->next)
	{
		int tx=now->x,nx;
		int ty=now->y,ny;
		int c;
		bool exist=0;

		PUT_POSS_BLACK[++PUT_NUM_BLACK].x=tx;
		PUT_POSS_BLACK[PUT_NUM_BLACK].y=ty;

		for (int d=0; d<8; d++)
		{
			for (nx=tx+PATH[d][0],ny=ty+PATH[d][1],c=0; MAP[nx][ny]==1 && 1<=nx && nx<=N && 1<=ny && ny<=N; nx+=PATH[d][0],ny+=PATH[d][1],c++);
			if (MAP[nx][ny]==2 && c>0) {PUT_POSS_BLACK[PUT_NUM_BLACK].dir[d]=1; exist=1;}
		}

		if (!exist) PUT_NUM_BLACK--;//delete
	}
}

void MAP::Can_drop_white(int P_MAP,POS_D* PUT_POSS_WHITE,POS* BORDER,int &PUT_NUM_WHITE) {

	PUT_NUM_WHITE=0;
	memset(PUT_POSS_WHITE,0,sizeof(POS_D)*257);

	for (POS* now=BORDER->next; now!=NULL; now=now->next)
	{
		int tx=now->x,nx;
		int ty=now->y,ny;
		int c;
		bool exist=0;

		PUT_POSS_WHITE[++PUT_NUM_WHITE].x=tx;
		PUT_POSS_WHITE[PUT_NUM_WHITE].y=ty;

		for (int d=0; d<8; d++)
		{
			for (nx=tx+PATH[d][0],ny=ty+PATH[d][1],c=0; MAP[nx][ny]==2 && 1<=nx && nx<=N && 1<=ny && ny<=N; nx+=PATH[d][0],ny+=PATH[d][1],c++);
			if (MAP[nx][ny]==1 && c>0) {PUT_POSS_WHITE[PUT_NUM_WHITE].dir[d]=1; exist=1;}
		}

		if (!exist) PUT_NUM_WHITE--;//delete
	}
}

//----------about the list

POS* MAP::Find(int x,int y,POS* BORDER) {

	POS* pos=0x0;
	for (POS* now=BORDER->next; now!=NULL; now=now->next)
		if (now->x==x && now->y==y)
		{
			pos=now;
			break;
		}
	return pos;
}

void MAP::Expand(int x,int y,POS* BORDER,int P_MAP) {

	POS* tmp;

	for (int d=0; d<8; d++)
	{
		int nx=x+DET[d][0];
		int ny=y+DET[d][1];
		if (1<=nx && nx<=N && 1<=ny && ny<=N)
			if ((MAP[nx][ny]!=1 && MAP[nx][ny]!=2) && (Find(nx,ny,BORDER)==NULL))
			{
				tmp=new POS;
				tmp->x=nx;
				tmp->y=ny;
				tmp->next=BORDER->next; BORDER->next=tmp;
			}//insert
	}
}

void MAP::Expand(int x,int y,POS* BORDER,int P_MAP,bool* dir) {

	POS* tmp;

	for (int d=0; d<8; d++)
	{
		int nx=x+DET[d][0];
		int ny=y+DET[d][1];
		if (1<=nx && nx<=N && 1<=ny && ny<=N)
			if ((MAP[nx][ny]!=1 && MAP[nx][ny]!=2) && (Find(nx,ny,BORDER)==NULL))
			{
				tmp=new POS;
				tmp->x=nx;
				tmp->y=ny;
				tmp->next=BORDER->next; BORDER->next=tmp;
				dir[d]=1;
			}//insert
	}
}

void MAP::Del(int x,int y,POS* BORDER) {

	POS* tmp;
	for (POS* now=BORDER; now->next!=NULL; now=now->next)
		if (now->next->x==x && now->next->y==y)
		{
			tmp=now->next;
			now->next=now->next->next;
			delete tmp;
			break;
		}
}

void MAP::Resume(int x,int y,POS *BORDER) {

	POS*tmp;
	tmp = new POS;
	tmp -> x = x; tmp -> y = y;
	tmp ->next = BORDER -> next;
	BORDER -> next = tmp;
}

void MAP::view(POS* BORDER) {

	for (POS* now=BORDER->next; now!=NULL; now=now->next) 
		std::cout<<now->x<<' '<<now->y<<std::endl;
}
